#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

// 合并两个递增链表为一个递减链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = createNode(0);  // 创建一个虚拟头节点
    ListNode* curr = dummy;

    // 当两个链表都不为空时
    while (l1 && l2) {
        // 如果 l1 的值大于 l2 的值
        if (l1->val > l2->val) {
            curr->next = l1;  // 将 l1 节点连接到结果链表
            l1 = l1->next;  // 移动 l1 指针
        } else {
            curr->next = l2;  // 将 l2 节点连接到结果链表
            l2 = l2->next;  // 移动 l2 指针
        }
        curr = curr->next;  // 移动结果链表指针
    }

    // 如果 l1 还有剩余节点，连接到结果链表
    if (l1) {
        curr->next = l1;
    }
    // 如果 l2 还有剩余节点，连接到结果链表
    if (l2) {
        curr->next = l2;
    }

    ListNode* newHead = dummy->next;  // 获取合并后的头节点
    free(dummy);  // 释放虚拟头节点

    // 反转合并后的链表
    ListNode* prev = NULL;
    curr = newHead;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }

    return prev;  // 返回反转后的头节点
}

int main() {
    // 构建第一个递增链表
    ListNode* l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);

    // 构建第二个递增链表
    ListNode* l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);

    ListNode* mergedList = mergeTwoLists(l1, l2);

    printf("合并后的递减链表: ");
    printList(mergedList);

    // 释放链表内存
    ListNode* temp;
    while (mergedList) {
        temp = mergedList;
        mergedList = mergedList->next;
        free(temp);
    }

    return 0;
}